package com.xiaoming.project.core;

public class SortTest {

    public static void main(String[] args) {
        int[] array = {18, 56, 11, -6, 10, 110, 4, 15, 77, 67, 42};
        // before
        printArray(array);

        // after
        quickSort(array, 0, array.length - 1);
        printArray(array);
    }

    private static void printArray(int[] array) {
        for (int tmp : array) {
            System.out.printf("%s,", tmp);
        }
        System.out.println();
    }

    /**
     * 排序类型：交换排序
     * 冒泡排序
     * 目的：每次编历整个数组，每次遍历选出当前数组最大的值
     * @param array
     * @return
     */
    public static int[] bubbleSort(int[] array) {
        return null;
    }

    /**
     * 排序类型：交换排序
     * 快速排序
     * 目的：每次找出中间的值，以中间值将数组分为两个小组，递归实现分组
     * 实现：从后、前交替编历，每次比较的结果都是一次大小的区分
     * 每次编历选出数组中间的值
     * @param array
     * @param left
     * @param right
     * @return
     */
    public static int[] quickSort(int[] array, int left, int right) {
        if (left > right) {
            return array;
        }

        int middle = array[left], tmpL = left, tmpR = right;
        while (tmpL < tmpR) {
            // 先右后左，利用中间比较的位置进行数据交换
            while (array[tmpR] > middle && tmpR > tmpL) {
                tmpR--;
            }
            array[tmpL] = array[tmpR];

            while (array[tmpL] < middle && tmpR > tmpL) {
                tmpL++;
            }
            array[tmpR] = array[tmpL];
        }
        array[tmpL] = middle;
        // 已经放在正确位置上的数不需要调整
        quickSort(array, left, tmpL - 1);
        quickSort(array, tmpL + 1, right);
        return array;
    }

    /**
     * 排序类型：插入排序
     * 简单插入排序
     * 目的：局部有序到整体有序
     * 实现：从左到右，每次编历找出当前值大小合适的位置（基于当前有序的局部数组）
     * @param array
     * @return
     */
    public static int[] simpleInsertSort(int[] array) {
        return null;
    }

    /**
     * 排序类型：插入排序
     * 希尔排序
     * 目的：减少插入排序时比较次数及数组整体移动次数
     * 实现：前期通过对数组分组进行比较排序，形成大致有序的数组，后再进行全体的排序
     * @param array
     * @return
     */
    public static int[] shellSort(int[] array) {
        return null;
    }

    /**
     * 排序类型：选择排序
     * 简单选择排序
     * @param array
     * @return
     */
    public static int[] simpleSelectSort(int[] array) {
        return null;
    }

    /**
     * 排序类型：选择排序
     * 堆排序
     * @param array
     * @return
     */
    public static int[] heapSort(int[] array) {
        return null;
    }

    /**
     * 排序类型：归并排序
     * @param array
     * @return
     */
    public static int[] mergeSort(int[] array) {
        return null;
    }

    /**
     * 排序类型：统计排序
     * @param array
     * @return
     */
    public static int[] countingSort(int[] array) {
        return null;
    }

    /**
     * 排序类型：桶排序
     * @param array
     * @return
     */
    public static int[] bucketSort(int[] array) {
        return null;
    }

    /**
     * 排序类型：基数排序
     * @param array
     * @return
     */
    public static int[] radixSort(int[] array) {
        return null;
    }

}
